The Alphabetical menu is used to create a binary tree containing an alphabetically sorted list of words. The scheme used to sort the words is as follows: each node holds one word; for any given node, the left pointer points to a subtree containing only words that come EARLIER in the alphabet; likewise, the right child and all its children hold words that come AFTER the given node's word.
Perhaps this can be made clearer by example: if you typed in "first", "second", "third", and "fourth" in that order, "first" would be the root of the tree, and "second" would be its right child. The word "third" would be the right child of "second". Next, "fourth" must lie down the right branch from "first", but left of "second", so it becomes the left child of "second".
At this point you may wish to build a tree yourself using Insert Word in the Alphabetical menu. Try guessing where the word will go before you type it in.
Once you have built up a tree, you may wish to find out whether particular word is in the tree. For example, the tree may hold every word in the dictionary, and you want to know whether "cow" is in the dictionary. When you type in the word, the computer moves down right and left branches (according to whether "cow" comes before or after the word at the fork) using EXACTLY the same method as if you were inserting "cow" for the first time. Since we follow the same path to find a word as we did when wefirst inserted it, we must eventually come to the node holding that word ("cow"). If the word isn't in the tree, we come to a dead end.
Try using Find Word before you read on.
Removing words is a bit tricky. You can't merely throw out the node; what if it has two children? (Also see the explanation of "Edit.") If the node doesn't have children, of course, we can just take it out, no harm done.
But say node A has one child. Then we take out node A, and we move the pointer that used to point to A so that it now points to A's child. You can see for yourself that this keeps the tree sorted.
Now say node A has two children. We can't just remove it, we must REPLACE it. But we must replace it with a word such that everything in the right subtree still comes after node A in the alphabet, and everything in the left still comes before node A. What word will satisfy this? The very next word alphabetically in the tree!
So to remove the word at a node having 2 children (call it node A), go down the right branch, then slide down every left branch (if any) until there are no more left branches. This node (node B) holds the word right after node A in the alphabet. Since node B has only a right child or no children, we can easily take it out of the tree. Now replace node A with node B. Presto! (Try it yourself... make sure you use the Normal Speed option in the Options menu.)
